from typing import List


class Solution:
    def sortArrayByParityII(self, A: List[int]) -> List[int]:
        A.sort()  # 先对数组进行排序
        i, j, ASize = 0, 1, len(A)  # 第一个指针,第二个指针,数组长度
        while i < ASize and j < ASize:  # 当第一个指针小于数组长度且第二个指针小于数组长度的时候
            # 不是偶数,就会停止循环,指向的一定是一个偶数
            while i < ASize and A[i] % 2 == 0:  # 当第一个指针小于长度,且指针指向的数是一个偶数的时候
                i += 2  # 每次加2,保证一直是偶数

            # 不是奇数,就会停止循环,指向的一定是一个奇数
            while j < ASize and A[j] % 2 == 1:  # 当第二个指针小于长度,且指针指向的数是一个奇数的时候
                j += 2  # 没加加2,保证一直是奇数

            if i < ASize and j < ASize:  # 如果第一个指针和第二个指针都小于长度
                # 交换奇数和偶数
                A[i], A[j] = A[j], A[i]  # 交换两个指针指向的值
        return A


# 输入：
l01 = [4, 2, 5, 7]
solution = Solution()
# 输出：[4, 5, 2, 7], [4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
print(solution.sortArrayByParityII(l01))
